public class Main {
    /**
     *求一个字符串中最长的数组子串
     */
//        public static void main(String[] args) {
//            Scanner in = new Scanner(System.in);
//            char[] str = in.next().toCharArray();
//            int n = str.length;
//            int len = 0;
//            int begin = 0;
//            for (int i = 0; i < n; i++) {
//                if (str[i] >= '0' && str[i] <= '9') {
//                    int j = i + 1;
//                    while (j < n) {
//                        if (str[j] >= '0' && str[j] <= '9') {
//                            j++;
//                        } else {
//                            if (len < j - i) {
//                                len = j - i;
//                                begin = i;
//                            }
//                            i = j;
//                            break;
//                        }
//                    }
//                    //细节: 注意处理最后因为全是数字然后循环跳出的情况 就无法进入else 修改len了
//                    if (j == n && str[j - 1] >= '0' && str[j - 1] <= '9') {
//                        if (len < j - i) {
//                            len = j - i;
//                            begin = i;
//                        }
//                    }
//                }
//            }
//            StringBuffer ret = new StringBuffer();
//            for (int i = begin; i < (begin + len); i++) {
//                ret.append(str[i]);
//            }
//            System.out.println(ret.toString());
//        }
//    }

/**
 * 爱丽丝的人偶
 */
//    public static void main(String[] args) {
//        Scanner in = new Scanner(System.in);
//        int n = in.nextInt();
//        //贪心
//        int left = 1;
//        int right = n;
//        int[] ret = new int [n];
//        for(int i = 0; i < n; i++) {
//            if(i % 2 == 0) {
//                //选最小的
//                ret[i] = left;
//                left++;
//            }else {
//                //选最大的
//                ret[i] = right;
//                right--;
//            }
//        }
//        for(int x : ret) {
//            System.out.print(x + " ");
//        }
//    }

    /**
     * 区间dp问题 最长回文子串
     */
//    public class Main {
//        public static void main(String[] args) {
//            Scanner in = new Scanner(System.in);
//            char[] str = in.next().toCharArray();
//            int n = str.length;
//            int[][] dp = new int[n][n];
//            for (int i = n - 1; i >= 0; i--) {
//                for (int j = 0; j < n; j++) {
//                    if (i > j) {
//                        dp[i][j] = 0;
//                    } else if (i == j) {
//                        dp[i][j] = 1;
//                    } else {
//                        dp[i][j] = (str[i] == str[j]) ? (dp[i + 1][j - 1] + 2) : Math.max(dp[i][j - 1], dp[i + 1][j]);
//                    }
//                }
//            }
//            System.out.println(dp[0][n - 1]);
//        }
//    }


//    public class Main {
//        public static void main(String[] args) {
//            Scanner in = new Scanner(System.in);
//            int n = in.nextInt();
//            int m = in.nextInt();
//            int[] arr1 = new int[n];
//            int[] arr2 = new int[m];
//            for (int i = 0; i < n; i++) {
//                arr1[i] = in.nextInt();
//            }
//            for (int i = 0; i < m; i++) {
//                arr2[i] = in.nextInt();
//            }
//            Arrays.sort(arr1);
//            Arrays.sort(arr2);
//            int cur1 = 0;
//            int cur2 = 0;
//            while (cur1 < n && cur2 < m) {
//                if (arr1[cur1] == arr2[cur2] ) {
//                    cur1++;
//                    continue;
//                } else if (arr1[cur1] < arr2[cur2] ) {
//                    System.out.print(arr1[cur1++] + " ");
//                } else {
//                    System.out.print(arr2[cur2++] + " ");
//                }
//            }
//            if (cur1 < n) {
//                for (int i = cur1; i < n; i++) {
//                    System.out.print(arr1[i] + " ");
//                }
//            } else {
//                for (int i = cur2; i < m; i++) {
//                    System.out.print(arr2[i] + " ");
//                }
//            }
//        }
//    }

    /**
     * 添加字符
     */
//    public class Main {
//        public static void main(String[] args) {
//            Scanner in = new Scanner(System.in);
//            //贪心
//            char[] strA = in.next().toCharArray();
//            char[] strB = in.next().toCharArray();
//            int n = strA.length;
//            int m = strB.length;
//            int ret = 0x3f3f3f3f;
//            for(int i = 0; i <= m - n; i++) {
//                int tmp = 0;
//                for(int j = 0; j < n; j++) {
//                    if(strA[j] != strB[j + i]) tmp++;
//                }
//                ret = Math.min(ret, tmp);
//            }
//            System.out.println(ret);
//        }
//    }

    /**
     * 装箱子问题
     */
//    public class Main {
//        public static void main(String[] args) {
//            Scanner in = new Scanner(System.in);
//            int V = in.nextInt();
//            int n = in.nextInt();
//            int[] arr = new int[n];
//            for (int i = 0; i < n; i++) {
//                arr[i] = in.nextInt();
//            }
//            int[][] dp = new int[n + 1][V + 1];
//            for (int i = 1; i <= n; i++) {
//                for (int j = 1; j <= V; j++) {
//                    dp[i][j] = Math.max(dp[i - 1][j],
//                            j - arr[i - 1] >= 0 ? dp[i - 1][j - arr[i - 1]] + arr[i - 1] : 0);
//                }
//            }
//            System.out.println(V - dp[n][V]);
//        }
//    }


    /**
     * 数组变换
     */
//    public class Main {
//        public static void main(String[] args) {
//            Scanner in = new Scanner(System.in);
//            int n = in.nextInt();
//            int[] arr = new int[n];
//            int maxNubmer = 0;
//            for (int i = 0; i < n; i++) {
//                int x = in.nextInt();
//                arr[i] = x;
//                if (x > maxNubmer) {
//                    maxNubmer = x;
//                }
//            }
//            boolean flag = true;
//            for (int x : arr) {
//                if (maxNubmer % x != 0) {
//                    flag = false;
//                    break;
//                }
//                int tmp = maxNubmer / x;
//                if ((tmp & (tmp - 1) ) !=  0) {
//                    flag = false;
//                    break;
//                }
//            }
//            if (flag == true) {
//                System.out.println("YES");
//            } else {
//                System.out.println("NO");
//            }
//        }
//    }

/**
 *打怪
 *发现循环的次数
 */
//    import java.util.*;
//
//    public class Main {
//        public static void main(String[] args) {
//            Scanner in = new Scanner(System.in);
//            int t = in.nextInt();
//            while (t-- > 0) {
//                int h = in.nextInt();
//                int a = in.nextInt();
//                int H = in.nextInt();
//                int A = in.nextInt();
//                if (a >= H)  {
//                    System.out.println(-1);
//                    continue;
//                }
//
//                int ret = 0;
//                //杀掉每次怪需要平a的次数
//                int m = H / a + (H % a != 0 ? 1 : 0);
//                ret = h / (A * (m - 1) ) - (h % (A * (m - 1) ) != 0 ? 0 : 1);
//                System.out.println(ret);
//            }
//        }
//    }

/**
 * 字符串的分类
 * 容器的应用
 */
//    public class Main {
//        public static void main(String[] args) {
//            Scanner in = new Scanner(System.in);
//            int n = in.nextInt();
//            Set<String> set = new HashSet<>();
//            for (int i = 0; i < n; i++) {
//                char[] str = in.next().toCharArray();
//                //先按照字典序排序然后扔进set中
//                Arrays.sort(str);//此处可以直接排 sort本身就就是按照字典序排序的
//                set.add(new String(str));
//            }
//            System.out.println(set.size());
//        }
//    }

/**
 *  城市群数
 */
//    public class Solution {
//        boolean[] visi;
//        int n;
//        int m;
//        public int citys (ArrayList<ArrayList<Integer>> grid) {
//            n = grid.size();
//            m = grid.get(0).size();
//            int ret = 0;
//            visi = new boolean[n];
//            for (int i = 0; i < n; i++) {
//                if (visi[i] == false) {
//                    ret++;
//                    bfs(grid, i);
//                }
//            }
//            return ret;
//        }
//        void bfs(ArrayList<ArrayList<Integer>> grid, int start) {
//            visi[start] = true;
//            Queue<Integer> queue = new LinkedList<>();
//            queue.add(start);
//            while (!queue.isEmpty()) {
//                int tmp = queue.poll();
//                //将所有的和tmp号城市相连的城市标记
//                for (int j = 0; j < n; j++) {
//                    if (visi[j] == false && grid.get(tmp).get(j) == 1) {
//                        visi[j] = true;
//                        //将j继续入队列 将所有和j相连的也标记了
//                        queue.add(j);
//                    }
//                }
//
//            }
//        }
//    }


}
